package chapter04_RecursionAndDynamic;

/**
 * 描述：跳跃游戏
 *      给定数组arr, arr[i]==k 代表可以从位置i向右跳1~k 个距离。比如，arr[2]==3， 代表
 *      从位置2可以跳到位置3、位置4或位置5。如果从位置0出发，返回最少跳几次能跳到arr最后的位置上。arr[i]>=1
 * @author hl
 * @date 2021/7/25 9:49
 */
public class Jump {
    public static void main(String[] args) {
        int[] arr = {3,2,3,1,1,4};
        Jump jump = new Jump();
        int res = jump.jump(arr);
        int res2 = jump.jump2(arr);
        System.out.println(res);
        System.out.println(res2);
    }

    /**
     * 最优解，遍历的过程递推下一跳能够到达的最远位置
     * @param arr
     * @return
     */
    public int jump(int [] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int jump = 0;//代表当前跳跃的步数
        int cur = 0;//表示jump能跳到的最远位置
        int next = 0;//代表下一条能跳到的最远位置
        for (int i = 0; i < arr.length; i++) {
            if (cur < i) {
                jump++;
                cur = next;
            }
            next = Math.max(next, i + arr[i]);
        }
        return jump;
    }

    public int jump3(int[] arr){
        int n = arr.length;
        int[] dp = new int[n];
        int steps = 0;
        for (int j = n - 2; j >= 0; j--) {
            if (dp[j] >= n - 1 - j) {
                dp[j] = 1;
            }else{
                steps = Integer.MAX_VALUE;
                for (int i = 1; i <= arr[j]; i++) {
                    steps = Math.min(steps, dp[j + i]);
                }
                dp[j] = steps + 1;
            }
        }
        return dp[0];
    }

    public int jump2(int[] arr){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    /**
     * 从l到r需要的最小步数
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= arr[l]; i++) {
            res = Math.min(process(arr, l + i, r) + 1, res);
        }
        return res;
    }
}
